/*************************************************************************
 * File Name: Populating_Next_Right_Pointers_in_Each_Node.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/4 12:31:46
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Populating Next Right Pointers in Each Node
 |
 | Given a binary tree
 |
 |  struct TreeLinkNode {
 |    TreeLinkNode *left;
 |    TreeLinkNode *right;
 |    TreeLinkNode *next;
 |  }
 | Populate each next pointer to point to its next right node. If there is
 | no next right node, the next pointer should be set to NULL.
 |
 | Initially, all next pointers are set to NULL.
 |
 | Note:
 |
 | You may only use constant extra space.
 | You may assume that it is a perfect binary tree (ie, all leaves are at the
 | same level, and every parent has two children).
 |
 | For example,
 | Given the following perfect binary tree,
 |       1
 |     /  \
 |    2    3
 |   / \  / \
 |  4  5  6  7
 | After calling your function, the tree should look like:
 |       1 -> NULL
 |     /  \
 |    2 -> 3 -> NULL
 |   / \  / \
 |  4->5->6->7 -> NULL
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root)
    {
        if (root == NULL) return;
        queue<pair<TreeLinkNode*,int> > Q;;
        Q.push(make_pair(root, 1));
        
        pair<TreeLinkNode*, int> pre(NULL,0);
        pair<TreeLinkNode*, int> p;
        while (!Q.empty()) {
            p = Q.front(), Q.pop();
            if (pre.second != p.second) {
                p.first->next = NULL;
            } else {
                p.first->next = pre.first;
            }
            
            if (p.first->right != NULL) Q.push(make_pair(p.first->right, p.second + 1));
            if (p.first->left != NULL) Q.push(make_pair(p.first->left, p.second + 1));
            pre = p;
        }
   }
};

